package solver

import (
	"gosudoku/set"
	"log"
	"math/rand"
	"time"
)

func (g *Grid) minCandidateCount() int {
	count := 9
	for _, row := range g.rows {
		for _, cell := range row.cells {
			if !cell.solved() && cell.cands.Count() < count {
				count = cell.cands.Count()
			}
		}
	}
	return count
}

func (g *Grid) selectMinUnsolved() []*Cell {
	minc := g.minCandidateCount()
	cells := []*Cell{}
	for _, row := range g.rows {
		for _, cell := range row.cells {
			if cell.solved() || cell.cands.Count() > minc {
				continue
			}
			cells = append(cells, cell)
		}
	}
	return cells
}

func (g *Grid) guessCell() (cell Cell) {
	cells := g.selectMinUnsolved()
	if len(cells) == 0 {
		return
	}
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	cell = *cells[r.Intn(len(cells))]
	return
}

func filledCorrentlyHouse(house House) bool {
	values := set.NewSet()
	for _, cell := range house.cells {
		if cell.solved() {
			values.Add(toCand(cell.value))
		} else {
			if cell.cands.Count() == 0 {
				return false
			}
		}
	}
	return values.Count() == house.solvedCount
}

func (g *Grid) filledCorrenctly() (ok bool) {
	for _, row := range g.rows {
		if !filledCorrentlyHouse(row) {
			return
		}
	}
	for _, col := range g.cols {
		if !filledCorrentlyHouse(col) {
			return
		}
	}
	for _, box := range g.boxes {
		if !filledCorrentlyHouse(box) {
			return
		}
	}
	ok = true
	return
}

/*
	type State struct {
		grid Grid
		cell Cell
	}
*/
type Stack[T any] []T

// Empty Stack
func (s *Stack[T]) IsEmpty() bool {
	return len(*s) == 0
}
func (s *Stack[T]) Push(v T) {
	*s = append(*s, v)
}

func (s *Stack[T]) Top() (v *T) {
	n := len(*s)
	v = &((*s)[n-1])
	return
}

func (s *Stack[T]) Pop() (v T) {
	n := len(*s)
	v = (*s)[n-1]
	*s = (*s)[:n-1]
	return
}

func (g *Grid) Backtrack() (used bool) {
	w := log.Writer()
	log.SetOutput(Discard{})
	cell := g.guessCell()
	result := backtrack(*g, cell)
	if result == nil {
		return false
	}
	*g = *result
	g.strategies = []Strategy{}
	log.SetOutput(w)
	log.Printf("Backtrack")
	return true
}
func backtrack(g Grid, cell Cell) (result *Grid) {
	g.Init()
	g.Clearup()
	if cell.cands.Count() == 0 {
		return nil
	}
	keep := g
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	cand := cell.cands.GetList()[r.Intn(cell.cands.Count())]
	//g.PrintGrid()
	//fmt.Println("cell=", cell, "cand=", cand)
	g.solveOneCell(cell.rowNum, cell.colNum, toValue(cand))
	sok := g.BasicSolver()
	if sok {
		if g.solvedCount == 81 {
			result = &g
			return
		} else {
			cell := g.guessCell()
			result = backtrack(g, cell)
			if result != nil {
				return
			}
			cell.cands.Delete(cand)
			return backtrack(keep, cell)
		}
	} else {
		cell.cands.Delete(cand)
		return backtrack(keep, cell)
	}
}

func (g *Grid) BasicSolver() (ok bool) {
	if !g.filledCorrenctly() {
		return
	}

	g.strategies = []Strategy{
		g.HiddenSingleBox,
		g.HiddenSingleRow,
		g.HiddenSingleCol,
		g.NakedSingle,
	}
	g.SolveForBack()

	return g.filledCorrenctly()
}

func mbacktrack(g Grid, results []Grid) []Grid {
	g.Init()
	g.Clearup()
	//fmt.Println("results", results)
	if !g.filledCorrenctly() {
		return []Grid{}
	}
	//fmt.Println("filledCorrenctly", g.filledCorrenctly())
	if !g.BasicSolver() {
		return []Grid{}
	}
	//fmt.Println("solvedCount", g.solvedCount)
	if g.solvedCount == 81 {
		results = append(results, g)
		return results
	}
	//fmt.Println("solvedCount", g.solvedCount)
	cell := g.guessCell()
	//fmt.Println("guess", cell)
	//fmt.Println("0-results=", len(results))
	for _, cand := range cell.cands.GetList() {
		//fmt.Println(cell, cand, len(results))
		x := g
		x.Init()
		x.Clearup()
		x.solveOneCell(cell.rowNum, cell.colNum, toValue(cand))
		r := mbacktrack(x, results)
		if len(r) > 0 {
			results = r
		}
	}
	//fmt.Println("1-results=", len(results))
	return results
}

func (g *Grid) MBacktrack() (used bool) {
	w := log.Writer()
	log.SetOutput(Discard{})
	results := []Grid{}
	results = mbacktrack(*g, results)
	log.SetOutput(w)
	n := len(results)
	switch {
	case n == 0:
		log.Println("can not be solved")
		return false
	case n == 1:
		*g = results[0]
		log.Println("Backtrack")
		return true
	default:
		log.Printf("There are %d results\n", len(results))
		//for _, r := range results {
		//	r.PrintGrid()
		//}
		*g = results[0]
		return false
	}
}
